package com.warningrc.demo;

import java.util.ArrayList;
import java.util.Stack;



public class DFS {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }
    public static void dfs(Node start) {
        // 创建一个栈，用于存储待访问的节点
        Stack<Node> stack = new Stack<>();
        // 创建一个布尔数组，用于标记节点是否已被访问，假设图中最多有100个节点，可根据实际情况调整大小
        boolean[] visited = new boolean[100];


        // 将起始节点压入栈中
        stack.push(start);
        // 标记起始节点为已访问
        visited[start.value] = true;

        // 当栈不为空时，循环执行以下操作
        while (!stack.isEmpty()) {
            // 取出栈顶节点，作为当前要访问的节点
            Node current = stack.pop();
            // 对当前节点进行处理，这里简单输出节点值
            System.out.print(current.value + " ");

            // 遍历当前节点的所有邻接节点
            for (Node neighbor : current.neighbors) {
                // 如果邻接节点未被访问
                if (!visited[neighbor.value]) {
                    // 将邻接节点压入栈中
                    stack.push(neighbor);
                    // 标记邻接节点为已访问
                    visited[neighbor.value] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 构建一个简单的图示例
        Node node0 = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        // node0的邻接节点有node1
        node0.neighbors.add(node1);
        // node0的邻接节点有node2
        node0.neighbors.add(node2);
        // node1的邻接节点有node2
        node1.neighbors.add(node2);
        // node2的邻接节点有node3
        node2.neighbors.add(node3);

        // 从node0开始进行深度优先搜索遍历
        dfs(node0);
    }
}